from typing import List


"""
给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在
数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
数组元素只可能有两种值。
"""
class Solution:
    """
    Boyer-Moore 投票算法：
    思路：把众数记为 +1，其他数记为 -1，将其全部加起来显然和大于 0。
    遍历数组，对于每个元素 x，如果此时的 count 值为 0，先将 x 赋值
    给 candidate，然后判断 x：
        若 x == candidate，则 count++；
        否则 count--。
    遍历完成后 candidate 为整个数组的众数。
    """
    def majorityElement(self, nums: List[int]) -> int:
        candidate = -1
        count = 0
        for n in nums:
            if n==candidate:
                count += 1
            else:
                count -= 1
                if count < 0:
                    candidate = n
                    count = 1
        
        return candidate
